#include "csp_base.h"

//domain operation

//delete value x from D_i

// this will return the dummyValue of the domain
// which acted as the value before the FIRST value and 
// after the LAST value. 
int CSP_base::headOfDomain() { return 0;}

// return the point to the domain of variable var.
Domain* CSP_base::domainOfVar(int var){
  return vars[var].dp; 
  // return domain + var*(d+1);
}

void CSP_base::printDomain(int var){
  Domain* dp;
  int value;
 
  cout << "domain[" << var << "] is: ";
  dp = domainOfVar(var); 
  value = dp[0].next;
  while (value != 0) {
    cout << value << ' ';
    value = dp[value].next;
  }
  cout << endl;
}

#if  defined(TAIL_DOMAIN) && defined(ORDERED_DOMAIN)
int CSP_base::next(int var, int value){
  Domain* dp;

  dp = domainOfVar(var); 
  value++;
  while(!dp[value].yes)  //there should always be a value greater than 0
  	value++;
  return value;
}
#else
int CSP_base::next(int var, int value){
  Domain* dp;

  dp = domainOfVar(var); 
  return dp[value].next; 
}
#endif


// The remove() has to gurantee this property:
// following the .next of a deleted value, we can either reach
// a value in the CURRENT domain or 0;
// following .pre field of a value, we can always find 
// a valid value before the value of concern, and we arrive at 0.
void CSP_base::remove(int i, int x)
{
  //cout << "Removing Value " << x << " from Variable " << i << " at phase " << curPhase << endl;//" due to " << (domainSplitting?"splitting":"MAC")<< endl;
	
  Domain *dp;
  
  dp = domainOfVar(i);
  //printf(" (%d.%d)", i, x);
  //printf("pre of x is %d and next of x is %d", dp[x].pre, dp[x].next);
  //getchar();
  //if(!dp[x].yes)
  //  cout << "FAILURE: REMOVAL OF A VALUE THAT IS ALREADY REMOVED: " << i << "," << x << endl;
  // print the removed values
  // if(i == 1) 
  // if (debugFlag)
  //   cout << "rm:" << i << '.' << x << ' ' << '\n';
  //  cout << " i.x=" << i << "." << x << ' ';
  // if (num_removed_values % 8 == 0) cout << "\n";

  num_removed_values++;
#ifdef EXTENDED_STATISTICS
  remval_levels[curPhase+1]++;
#endif
  // std::cout << '(' << i << ',' << x << ')' ;
  //if (num_removed_values % 100 == 0 ) printf("%d ",num_removed_values);
  //if (num_removed_values % 15 == 0 ) std::cout << "\n"; 

#ifdef BACK_POINT_SUPPORT
  //cout << "Transfering support to " << dp[x].pre << endl;
  BackSupportNode* ds;
  ds = dp[x].supported;
  BackSupport.transferSupport(dp,ds,dp[x].pre);
  dp[x].supported=NULL;
#endif

#ifdef FORW_POINT_SUPPORT
#ifdef AC3ADO

  ForwSupportNode* ds;
  Support rs;
  while(dp[x].supported!=NULL)
  {
	  ds=dp[x].supported;
	  rs=support[(ds->varia)*n+i];
	  rs[ds->value-1]=dp[x].next;
	  ForwSupport.moveSupport(dp,x,dp[x].next,ds);
  }
#endif
#endif

  dp[ x ].yes = 0;
  dp[dp[x].pre].next = dp[x].next;
  dp[dp[x].next].pre = dp[x].pre;

  vars[i].domainSize--; // this value is not backuped, its restored by recompute it.

  //--------backup the removed values---------------
  RemovedValue rmValue;
                                                                                
  rmValue.var = i;
  rmValue.value = x;
  rmValue.phase = curPhase;
#ifdef DOMAIN_SPLIT
  if(domainSplitting)
  {
	rmValue.seg=curSeg;
	splitValues.push(rmValue);
  }
  else
#endif
	removedValues.push(rmValue);
}


#if defined(TAIL_DOMAIN)

void CSP_base::insert(int var,int value) {

	//cout << "Restoring Value " << value << " to Variable " << var << " at phase " << curPhase << endl;// << " due to " << (domainSplitting?"splitting":"MAC")<< endl;
	Domain *dp;
	dp= domainOfVar(var);

	int end=dp[0].pre;

	dp[0].pre=value;
	dp[value].next=0;
	dp[end].next=value;
	dp[value].pre=end;
	dp[value].yes=1;

	vars[var].domainSize++;
}

#else
// insert a value of a variable back to its domain
// the original odering is maintained in this insertion
void CSP_base::insert(int var, int value) {

  //cout << "Restoring Value " << value << " to Variable " << var << " at phase " << curPhase << endl;// << " due to " << (domainSplitting?"splitting":"MAC")<< endl;
  int curPos = headOfDomain(), nextV;
  Domain* dp;
  //int dummyValue = curPos; 
                                                                                
  dp = domainOfVar(var); 
  //if(dp[value].yes)
  //  cout << "FAILURE: INSERTING VALUE THAT IS ALREADY AVAILABLE: " << var << "," << value << endl;
  // find the position for insertion

  //OLD CODE: this is the old way of performing insertion
  //while( (dp[curPos].next != dummyValue) && (dp[curPos].next < value)) {
  //  curPos = dp[curPos].next;
  //}
  //NEW CODE: testing new way by checking backwards
  //because values are generally removed left to right,
  //by searching right to left, it is more likely to hit
  //the correct position.
  curPos=value-1; //value-1 should be the value to the right
					//this should never cause conflicts, and
					//saves one "domain check" per insertion
  while( !(dp[curPos].yes)) curPos--;
  //END NEW CODE
                                                                                
  dp[value].yes = 1;
  dp[value].pre = curPos;
  nextV = dp[curPos].next;
  dp[value].next = nextV;
  dp[curPos].next = value;
  dp[nextV].pre = value;

  vars[var].domainSize++; 
}
#endif
// When putting back the removed values to its original
// domain, we need to keep an ordering among the values.
// The values before (not including) 'phase' will be 
// restored.
void CSP_base::restoreDomains(int phase){
  RemovedValue rmValue;
#ifdef DOMAIN_SPLIT
  std::stack<RemovedValue>& valueStack=(domainSplitting?splitValues:removedValues);
#else
  std::stack<RemovedValue>& valueStack=removedValues;
#endif
  while(!valueStack.empty()){
    rmValue = valueStack.top();	
#ifdef DOMAIN_SPLIT
    if(rmValue.phase < phase || (domainSplitting && rmValue.seg <curSeg))
	{
		//if(domainSplitting)
		//{
		//	cout << "No more restorations for " << phase << "," << curSeg << endl;
		//	cout << "Top of Stack: " << rmValue.phase << "," << rmValue.seg << endl;
		//}
		break; //no more states to restore
	}
#else
	if(rmValue.phase < phase) break; //no more states to restore
#endif
    insert( rmValue.var, rmValue.value );
    valueStack.pop();
  } //end of while loop to restore values in the stack
}

bool CSP_base::empty_domain(int i)
{
  //Domain *dp;
  
  //dp = domain + i*(d+1);
  //if (dp[0].next == 0) {
    // std::cout << "[CSP_base::empty_domain] " << "domain of x" << i << " is wiped out\n";
  //  return 1; // empty
  //}
  //else return 0; // non empty
  return vars[i].domainSize==0; //simpler, same result as above code
}

// set the clock in csp
void CSP_base::setPhase(int phase){
  curPhase = phase;
  //cout << "Phase = " << curPhase << endl;
}

void CSP_base::initCSP_base()
{

  // cross_link_list is an efficient representation of
  // the relationship between variables and constraints.
  // Given a variable, we can immediately get all constraints
  // on this variable by using the cross_link_list.
  cross_link_list = new list<int> [n];
#ifdef VAL_COMPUTE
  valConnect.resize(n*d);
  valConflict.resize(n*d);
#endif
  if (!cross_link_list){
    cout << "Mem Allocation Error.\n";
    exit(-1);
  }

  //cout << "Creating Link List and Value List" << endl;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++ ){
#ifdef VAL_COMPUTE
	  if(i==j){
		for(int x=0;x<d;x++)
			valConflict[i*d+x].push_back(i*d+x);
	  }
#endif
      if (related(i, j)){ // if there is a constraint between i and j
		cross_link_list[i].push_back(j);
		//cout << "On Variable Pair (" << i << "," << j << ")" << endl;
#ifdef VAL_COMPUTE
		for(int x=0;x<d;x++){
			for(int y=0;y<d;y++){
				//cout << "On Value Pair (" << x << "," << y << ")" << endl;
				if(validtuple(i,j,x+1,y+1)){
					valConnect[i*d+x].push_back(j*d+y);
				}
				else{
					valConflict[i*d+x].push_back(j*d+y);
				}
				
			}
		}
#endif
	  }// else do nothing 
    } // constraint (i,j)
	vars[i].degree=cross_link_list[i].size(); //CHANGED FOR DEGREE FINDING
  }
  //cout << "Finished Initializing lists" << endl;
}


CSP_base::CSP_base()
{
  //cerr << "Constructor: CSP_base begin" << endl;
  // initialize the statistics
  num_removed_values = 0;
  num_cchecks = 0;
  num_cchecks_M = 0;
  num_dchecks = 0;
  num_dchecks_M = 0;
  // for k-residue
  num_ochecks = 0;
  num_ochecks_M = 0; 

#ifdef EXTENDED_STATISTICS
  //cout << "extended statistic creation/initialization" << endl;
  ccheck_levels=new int[n+1];
  dcheck_levels=new int[n+1];
  remval_levels=new int[n+1];
  for(int i=0;i<n+1;i++) {ccheck_levels[i]=dcheck_levels[i]=remval_levels[i]=0;}
  //cout << "done" << endl;
#endif
#ifdef DOMAIN_SPLIT
  domainSplitting=false;
  int curSeg=0;
#endif
  //cerr << "Constructor: CSP_base end" << endl;
}

CSP_base::~CSP_base()
{
  //cerr << "Destructor: CSP_base begin" << endl;
  // cross_link_list created in initCSP_base
  if (cross_link_list != NULL)  delete [] cross_link_list;
#ifdef EXTENDED_STATISTICS
  if (ccheck_levels != NULL)  delete [] ccheck_levels;
  if (dcheck_levels != NULL)  delete [] dcheck_levels;
#endif
  //cerr << "Destructor: CSP_base end" << endl;
}
